home *** CD-ROM | disk | FTP | other *** search
/ BBS in a Box 15 / BBS in a box XV-2.iso / Files II / Prog / M / MacPerl 4.13 source.sit / Perl Source ƒ / Perl / regcomp.c / regcomp.c
Encoding:
C/C++ Source or Header  |  1993-10-23  |  32.7 KB  |  1,512 lines  |  [TEXT/MPS ]
  1. /* NOTE: this is derived from Henry Spencer's regexp code, and should not
  2.  * confused with the original package (see point 3 below).  Thanks, Henry!
  3.  */
  4.  
  5. /* Additional note: this code is very heavily munged from Henry's version
  6.  * in places.  In some spots I've traded clarity for efficiency, so don't
  7.  * blame Henry for some of the lack of readability.
  8.  */
  9.  
  10. /* $RCSfile: regcomp.c,v $$Revision: 4.0.1.5 $$Date: 92/06/08 15:23:36 $
  11.  *
  12.  * $Log:    regcomp.c,v $
  13.  * Revision 4.0.1.5  92/06/08  15:23:36  lwall
  14.  * patch20: Perl now distinguishes overlapped copies from non-overlapped
  15.  * patch20: /^stuff/ wrongly assumed an implicit $* == 1
  16.  * patch20: /x{0}/ was wrongly interpreted as /x{0,}/
  17.  * patch20: added \W, \S and \D inside /[...]/
  18.  * 
  19.  * Revision 4.0.1.4  91/11/05  22:55:14  lwall
  20.  * patch11: Erratum
  21.  * 
  22.  * Revision 4.0.1.3  91/11/05  18:22:28  lwall
  23.  * patch11: minimum match length calculation in regexp is now cumulative
  24.  * patch11: initial .* in pattern had dependency on value of $*
  25.  * patch11: certain patterns made use of garbage pointers from uncleared memory
  26.  * patch11: prepared for ctype implementations that don't define isascii()
  27.  * 
  28.  * Revision 4.0.1.2  91/06/07  11:48:24  lwall
  29.  * patch4: new copyright notice
  30.  * patch4: /(x+) \1/ incorrectly optimized to not match "xxx xx"
  31.  * patch4: // wouldn't use previous pattern if it started with a null character
  32.  * 
  33.  * Revision 4.0.1.1  91/04/12  09:04:45  lwall
  34.  * patch1: random cleanup in cpp namespace
  35.  * 
  36.  * Revision 4.0  91/03/20  01:39:01  lwall
  37.  * 4.0 baseline.
  38.  * 
  39.  */
  40. /*SUPPRESS 112*/
  41. /*
  42.  * regcomp and regexec -- regsub and regerror are not used in perl
  43.  *
  44.  *    Copyright (c) 1986 by University of Toronto.
  45.  *    Written by Henry Spencer.  Not derived from licensed software.
  46.  *
  47.  *    Permission is granted to anyone to use this software for any
  48.  *    purpose on any computer system, and to redistribute it freely,
  49.  *    subject to the following restrictions:
  50.  *
  51.  *    1. The author is not responsible for the consequences of use of
  52.  *        this software, no matter how awful, even if they arise
  53.  *        from defects in it.
  54.  *
  55.  *    2. The origin of this software must not be misrepresented, either
  56.  *        by explicit claim or by omission.
  57.  *
  58.  *    3. Altered versions must be plainly marked as such, and must not
  59.  *        be misrepresented as being the original software.
  60.  *
  61.  *
  62.  ****    Alterations to Henry's code are...
  63.  ****
  64.  ****    Copyright (c) 1991, Larry Wall
  65.  ****
  66.  ****    You may distribute under the terms of the Perl Artistic License,
  67.  ****    as specified in the README file.
  68.  
  69.  *
  70.  * Beware that some of this code is subtly aware of the way operator
  71.  * precedence is structured in regular expressions.  Serious changes in
  72.  * regular-expression syntax might require a total rethink.
  73.  */
  74. #include "EXTERN.h"
  75. #include "perl.h"
  76. #include "INTERN.h"
  77. #include "regcomp.h"
  78.  
  79. #ifdef MSDOS
  80. # if defined(BUGGY_MSC6)
  81.  /* MSC 6.00A breaks on op/regexp.t test 85 unless we turn this off */
  82.  # pragma optimize("a",off)
  83.  /* But MSC 6.00A is happy with 'w', for aliases only across function calls*/
  84.  # pragma optimize("w",on )
  85. # endif /* BUGGY_MSC6 */
  86. #endif /* MSDOS */
  87.  
  88. #ifndef STATIC
  89. #define    STATIC    static
  90. #endif
  91.  
  92. #define    ISMULT1(c)    ((c) == '*' || (c) == '+' || (c) == '?')
  93. #define    ISMULT2(s)    ((*s) == '*' || (*s) == '+' || (*s) == '?' || \
  94.     ((*s) == '{' && regcurly(s)))
  95. #ifdef atarist
  96. #define    PERL_META    "^$.[()|?+*\\"
  97. #else
  98. #define    META    "^$.[()|?+*\\"
  99. #endif
  100.  
  101. #ifdef SPSTART
  102. #undef SPSTART        /* dratted cpp namespace... */
  103. #endif
  104. /*
  105.  * Flags to be passed up and down.
  106.  */
  107. #define    HASWIDTH    01    /* Known never to match null string. */
  108. #define    SIMPLE        02    /* Simple enough to be STAR/PLUS operand. */
  109. #define    SPSTART        04    /* Starts with * or +. */
  110. #define    WORST        0    /* Worst case. */
  111.  
  112. /*
  113.  * Global work variables for regcomp().
  114.  */
  115. static char *regprecomp;        /* uncompiled string. */
  116. static char *regparse;        /* Input-scan pointer. */
  117. static char *regxend;        /* End of input for compile */
  118. static int regnpar;        /* () count. */
  119. static char *regcode;        /* Code-emit pointer; ®dummy = don't. */
  120. static long regsize;        /* Code size. */
  121. static int regfold;
  122. static int regsawbracket;    /* Did we do {d,d} trick? */
  123. static int regsawback;        /* Did we see \1, ...? */
  124.  
  125. /*
  126.  * Forward declarations for regcomp()'s friends.
  127.  */
  128. STATIC int regcurly();
  129. STATIC char *reg();
  130. STATIC char *regbranch();
  131. STATIC char *regpiece();
  132. STATIC char *regatom();
  133. STATIC char *regclass();
  134. STATIC char *regnode();
  135. STATIC char *reganode();
  136. STATIC void regc();
  137. STATIC void reginsert();
  138. STATIC void regtail();
  139. STATIC void regoptail();
  140.  
  141. /*
  142.  - regcomp - compile a regular expression into internal code
  143.  *
  144.  * We can't allocate space until we know how big the compiled form will be,
  145.  * but we can't compile it (and thus know how big it is) until we've got a
  146.  * place to put the code.  So we cheat:  we compile it twice, once with code
  147.  * generation turned off and size counting turned on, and once "for real".
  148.  * This also means that we don't allocate space until we are sure that the
  149.  * thing really will compile successfully, and we never have to move the
  150.  * code and thus invalidate pointers into it.  (Note that it has to be in
  151.  * one piece because free() must be able to free it all.) [NB: not true in perl]
  152.  *
  153.  * Beware that the optimization-preparation code in here knows about some
  154.  * of the structure of the compiled regexp.  [I'll say.]
  155.  */
  156. regexp *
  157. regcomp(exp,xend,fold)
  158. char *exp;
  159. char *xend;
  160. int fold;
  161. {
  162.     register regexp *r;
  163.     register char *scan;
  164.     register STR *longish;
  165.     STR *longest;
  166.     register int len;
  167.     register char *first;
  168.     int flags;
  169.     int backish;
  170.     int backest;
  171.     int curback;
  172.     int minlen;
  173.     int sawplus = 0;
  174.     int sawopen = 0;
  175.  
  176.     if (exp == NULL)
  177.         fatal("NULL regexp argument");
  178.  
  179.     /* First pass: determine size, legality. */
  180.     regfold = fold;
  181.     regparse = exp;
  182.     regxend = xend;
  183.     regprecomp = nsavestr(exp,xend-exp);
  184.     regsawbracket = 0;
  185.     regsawback = 0;
  186.     regnpar = 1;
  187.     regsize = 0L;
  188.     regcode = ®dummy;
  189.     regc((char)MAGIC);
  190.     if (reg(0, &flags) == NULL) {
  191.         Safefree(regprecomp);
  192.         regprecomp = Nullch;
  193.         return(NULL);
  194.     }
  195.  
  196.     /* Small enough for pointer-storage convention? */
  197.     if (regsize >= 32767L)        /* Probably could be 65535L. */
  198.         FAIL("regexp too big");
  199.  
  200.     /* Allocate space. */
  201.     Newc(1001, r, sizeof(regexp) + (unsigned)regsize, char, regexp);
  202.     if (r == NULL)
  203.         FAIL("regexp out of space");
  204.  
  205.     /* Second pass: emit code. */
  206.     if (regsawbracket)
  207.         Copy(regprecomp,exp,xend-exp,char);
  208.     r->prelen = xend-exp;
  209.     r->precomp = regprecomp;
  210.     r->subbeg = r->subbase = NULL;
  211.     regparse = exp;
  212.     regnpar = 1;
  213.     regcode = r->program;
  214.     regc((char)MAGIC);
  215.     if (reg(0, &flags) == NULL)
  216.         return(NULL);
  217.  
  218.     /* Dig out information for optimizations. */
  219.     r->regstart = Nullstr;    /* Worst-case defaults. */
  220.     r->reganch = 0;
  221.     r->regmust = Nullstr;
  222.     r->regback = -1;
  223.     r->regstclass = Nullch;
  224.     scan = r->program+1;            /* First BRANCH. */
  225.     if (OP(regnext(scan)) == END) {/* Only one top-level choice. */
  226.         scan = NEXTOPER(scan);
  227.  
  228.         first = scan;
  229.         while ((OP(first) == OPEN && (sawopen = 1)) ||
  230.             (OP(first) == BRANCH && OP(regnext(first)) != BRANCH) ||
  231.             (OP(first) == PLUS) ||
  232.             (OP(first) == CURLY && ARG1(first) > 0) ) {
  233.             if (OP(first) == PLUS)
  234.                 sawplus = 1;
  235.             else
  236.                 first += regarglen[OP(first)];
  237.             first = NEXTOPER(first);
  238.         }
  239.  
  240.         /* Starting-point info. */
  241.         again:
  242.         if (OP(first) == EXACTLY) {
  243.             r->regstart =
  244.                 str_make(OPERAND(first)+1,*OPERAND(first));
  245.             if (r->regstart->str_cur > !(sawstudy|fold))
  246.                 fbmcompile(r->regstart,fold);
  247.         }
  248.         else if ((exp = index(simple,OP(first))) && exp > simple)
  249.             r->regstclass = first;
  250.         else if (OP(first) == BOUND || OP(first) == NBOUND)
  251.             r->regstclass = first;
  252.         else if (OP(first) == BOL) {
  253.             r->reganch = ROPT_ANCH;
  254.             first = NEXTOPER(first);
  255.                 goto again;
  256.         }
  257.         else if ((OP(first) == STAR && OP(NEXTOPER(first)) == ANY) &&
  258.              !(r->reganch & ROPT_ANCH) ) {
  259.             /* turn .* into ^.* with an implied $*=1 */
  260.             r->reganch = ROPT_ANCH | ROPT_IMPLICIT;
  261.             first = NEXTOPER(first);
  262.                 goto again;
  263.         }
  264.         if (sawplus && (!sawopen || !regsawback))
  265.             r->reganch |= ROPT_SKIP;    /* x+ must match 1st of run */
  266.  
  267. #ifdef DEBUGGING
  268. #ifdef macintosh
  269.         if (debug & 512)
  270.             fprintf(perldbg,"first %d next %d offset %d\n",
  271.               OP(first), OP(NEXTOPER(first)), first - scan);
  272. #else
  273.         if (debug & 512)
  274.             fprintf(stderr,"first %d next %d offset %d\n",
  275.               OP(first), OP(NEXTOPER(first)), first - scan);
  276. #endif
  277. #endif
  278.         /*
  279.          * If there's something expensive in the r.e., find the
  280.          * longest literal string that must appear and make it the
  281.          * regmust.  Resolve ties in favor of later strings, since
  282.          * the regstart check works with the beginning of the r.e.
  283.          * and avoiding duplication strengthens checking.  Not a
  284.          * strong reason, but sufficient in the absence of others.
  285.          * [Now we resolve ties in favor of the earlier string if
  286.          * it happens that curback has been invalidated, since the
  287.          * earlier string may buy us something the later one won't.]
  288.          */
  289.         longish = str_make("",0);
  290.         longest = str_make("",0);
  291.         len = 0;
  292.         minlen = 0;
  293.         curback = 0;
  294.         backish = 0;
  295.         backest = 0;
  296.         while (OP(scan) != END) {
  297.             if (OP(scan) == BRANCH) {
  298.                 if (OP(regnext(scan)) == BRANCH) {
  299.                 curback = -30000;
  300.                 while (OP(scan) == BRANCH)
  301.                     scan = regnext(scan);
  302.                 }
  303.                 else    /* single branch is ok */
  304.                 scan = NEXTOPER(scan);
  305.             }
  306.             if (OP(scan) == EXACTLY) {
  307.                 char *t;
  308.  
  309.                 first = scan;
  310.                 while (OP(t = regnext(scan)) == CLOSE)
  311.                 scan = t;
  312.                 minlen += *OPERAND(first);
  313.                 if (curback - backish == len) {
  314.                 str_ncat(longish, OPERAND(first)+1,
  315.                     *OPERAND(first));
  316.                 len += *OPERAND(first);
  317.                 curback += *OPERAND(first);
  318.                 first = regnext(scan);
  319.                 }
  320.                 else if (*OPERAND(first) >= len + (curback >= 0)) {
  321.                 len = *OPERAND(first);
  322.                 str_nset(longish, OPERAND(first)+1,len);
  323.                 backish = curback;
  324.                 curback += len;
  325.                 first = regnext(scan);
  326.                 }
  327.                 else
  328.                 curback += *OPERAND(first);
  329.             }
  330.             else if (index(varies,OP(scan))) {
  331.                 curback = -30000;
  332.                 len = 0;
  333.                 if (longish->str_cur > longest->str_cur) {
  334.                 str_sset(longest,longish);
  335.                 backest = backish;
  336.                 }
  337.                 str_nset(longish,"",0);
  338.                 if (OP(scan) == PLUS &&
  339.                   index(simple,OP(NEXTOPER(scan))))
  340.                 minlen++;
  341.                 else if (OP(scan) == CURLY &&
  342.                   index(simple,OP(NEXTOPER(scan)+4)))
  343.                 minlen += ARG1(scan);
  344.             }
  345.             else if (index(simple,OP(scan))) {
  346.                 curback++;
  347.                 minlen++;
  348.                 len = 0;
  349.                 if (longish->str_cur > longest->str_cur) {
  350.                 str_sset(longest,longish);
  351.                 backest = backish;
  352.                 }
  353.                 str_nset(longish,"",0);
  354.             }
  355.             scan = regnext(scan);
  356.         }
  357.  
  358.         /* Prefer earlier on tie, unless we can tail match latter */
  359.  
  360.         if (longish->str_cur + (OP(first) == EOL) > longest->str_cur) {
  361.             str_sset(longest,longish);
  362.             backest = backish;
  363.         }
  364.         else
  365.             str_nset(longish,"",0);
  366.         if (longest->str_cur
  367.             &&
  368.             (!r->regstart
  369.              ||
  370.              !fbminstr((unsigned char*) r->regstart->str_ptr,
  371.               (unsigned char *) r->regstart->str_ptr
  372.                 + r->regstart->str_cur,
  373.               longest)
  374.             )
  375.            )
  376.         {
  377.             r->regmust = longest;
  378.             if (backest < 0)
  379.                 backest = -1;
  380.             r->regback = backest;
  381.             if (longest->str_cur
  382.               > !(sawstudy || fold || OP(first) == EOL) )
  383.                 fbmcompile(r->regmust,fold);
  384.             r->regmust->str_u.str_useful = 100;
  385.             if (OP(first) == EOL && longish->str_cur)
  386.                 r->regmust->str_pok |= SP_TAIL;
  387.         }
  388.         else {
  389.             str_free(longest);
  390.             longest = Nullstr;
  391.         }
  392.         str_free(longish);
  393.     }
  394.  
  395.     r->do_folding = fold;
  396.     r->nparens = regnpar - 1;
  397.     r->minlen = minlen;
  398.     Newz(1002, r->startp, regnpar, char*);
  399.     Newz(1002, r->endp, regnpar, char*);
  400. #ifdef DEBUGGING
  401.     if (debug & 512)
  402.         regdump(r);
  403. #endif
  404.     return(r);
  405. }
  406.  
  407. /*
  408.  - reg - regular expression, i.e. main body or parenthesized thing
  409.  *
  410.  * Caller must absorb opening parenthesis.
  411.  *
  412.  * Combining parenthesis handling with the base level of regular expression
  413.  * is a trifle forced, but the need to tie the tails of the branches to what
  414.  * follows makes it hard to avoid.
  415.  */
  416. static char *
  417. reg(paren, flagp)
  418. int paren;            /* Parenthesized? */
  419. int *flagp;
  420. {
  421.     register char *ret;
  422.     register char *br;
  423.     register char *ender;
  424.     register int parno;
  425.     int flags;
  426.  
  427.     *flagp = HASWIDTH;    /* Tentatively. */
  428.  
  429.     /* Make an OPEN node, if parenthesized. */
  430.     if (paren) {
  431.         parno = regnpar;
  432.         regnpar++;
  433.         ret = reganode(OPEN, parno);
  434.     } else
  435.         ret = NULL;
  436.  
  437.     /* Pick up the branches, linking them together. */
  438.     br = regbranch(&flags);
  439.     if (br == NULL)
  440.         return(NULL);
  441.     if (ret != NULL)
  442.         regtail(ret, br);    /* OPEN -> first. */
  443.     else
  444.         ret = br;
  445.     if (!(flags&HASWIDTH))
  446.         *flagp &= ~HASWIDTH;
  447.     *flagp |= flags&SPSTART;
  448.     while (*regparse == '|') {
  449.         regparse++;
  450.         br = regbranch(&flags);
  451.         if (br == NULL)
  452.             return(NULL);
  453.         regtail(ret, br);    /* BRANCH -> BRANCH. */
  454.         if (!(flags&HASWIDTH))
  455.             *flagp &= ~HASWIDTH;
  456.         *flagp |= flags&SPSTART;
  457.     }
  458.  
  459.     /* Make a closing node, and hook it on the end. */
  460.     if (paren)
  461.         ender = reganode(CLOSE, parno);
  462.     else
  463.         ender = regnode(END);
  464.     regtail(ret, ender);
  465.  
  466.     /* Hook the tails of the branches to the closing node. */
  467.     for (br = ret; br != NULL; br = regnext(br))
  468.         regoptail(br, ender);
  469.  
  470.     /* Check for proper termination. */
  471.     if (paren && *regparse++ != ')') {
  472.         FAIL("unmatched () in regexp");
  473.     } else if (!paren && regparse < regxend) {
  474.         if (*regparse == ')') {
  475.             FAIL("unmatched () in regexp");
  476.         } else
  477.             FAIL("junk on end of regexp");    /* "Can't happen". */
  478.         /* NOTREACHED */
  479.     }
  480.  
  481.     return(ret);
  482. }
  483.  
  484. /*
  485.  - regbranch - one alternative of an | operator
  486.  *
  487.  * Implements the concatenation operator.
  488.  */
  489. static char *
  490. regbranch(flagp)
  491. int *flagp;
  492. {
  493.     register char *ret;
  494.     register char *chain;
  495.     register char *latest;
  496.     int flags;
  497.  
  498.     *flagp = WORST;        /* Tentatively. */
  499.  
  500.     ret = regnode(BRANCH);
  501.     chain = NULL;
  502.     while (regparse < regxend && *regparse != '|' && *regparse != ')') {
  503.         latest = regpiece(&flags);
  504.         if (latest == NULL)
  505.             return(NULL);
  506.         *flagp |= flags&HASWIDTH;
  507.         if (chain == NULL)    /* First piece. */
  508.             *flagp |= flags&SPSTART;
  509.         else
  510.             regtail(chain, latest);
  511.         chain = latest;
  512.     }
  513.     if (chain == NULL)    /* Loop ran zero times. */
  514.         (void) regnode(NOTHING);
  515.  
  516.     return(ret);
  517. }
  518.  
  519. /*
  520.  - regpiece - something followed by possible [*+?]
  521.  *
  522.  * Note that the branching code sequences used for ? and the general cases
  523.  * of * and + are somewhat optimized:  they use the same NOTHING node as
  524.  * both the endmarker for their branch list and the body of the last branch.
  525.  * It might seem that this node could be dispensed with entirely, but the
  526.  * endmarker role is not redundant.
  527.  */
  528. static char *
  529. regpiece(flagp)
  530. int *flagp;
  531. {
  532.     register char *ret;
  533.     register char op;
  534.     register char *next;
  535.     int flags;
  536.     char *origparse = regparse;
  537.     int orignpar = regnpar;
  538.     char *max;
  539.     int iter;
  540.     char ch;
  541.  
  542.     ret = regatom(&flags);
  543.     if (ret == NULL)
  544.         return(NULL);
  545.  
  546.     op = *regparse;
  547.  
  548.     /* Here's a total kludge: if after the atom there's a {\d+,?\d*}
  549.      * then we decrement the first number by one and reset our
  550.      * parsing back to the beginning of the same atom.  If the first number
  551.      * is down to 0, decrement the second number instead and fake up
  552.      * a ? after it.  Given the way this compiler doesn't keep track
  553.      * of offsets on the first pass, this is the only way to replicate
  554.      * a piece of code.  Sigh.
  555.      */
  556.     if (op == '{' && regcurly(regparse)) {
  557.         next = regparse + 1;
  558.         max = Nullch;
  559.         while (isDIGIT(*next) || *next == ',') {
  560.         if (*next == ',') {
  561.             if (max)
  562.             break;
  563.             else
  564.             max = next;
  565.         }
  566.         next++;
  567.         }
  568.         if (*next == '}') {        /* got one */
  569.         if (!max)
  570.             max = next;
  571.         regparse++;
  572.         iter = atoi(regparse);
  573.         if (flags&SIMPLE) {    /* we can do it right after all */
  574.             int tmp;
  575.  
  576.             reginsert(CURLY, ret);
  577.             if (iter > 0)
  578.             *flagp = (WORST|HASWIDTH);
  579.             if (*max == ',')
  580.             max++;
  581.             else
  582.             max = regparse;
  583.             tmp = atoi(max);
  584.             if (!tmp && *max != '0')
  585.             tmp = 32767;        /* meaning "infinity" */
  586.             if (tmp && tmp < iter)
  587.             fatal("Can't do {n,m} with n > m");
  588.             if (regcode != ®dummy) {
  589. #ifdef REGALIGN
  590.             *(unsigned short *)(ret+3) = iter;
  591.             *(unsigned short *)(ret+5) = tmp;
  592. #else
  593.             ret[3] = iter >> 8; ret[4] = iter & 0377;
  594.             ret[5] = tmp  >> 8; ret[6] = tmp  & 0377;
  595. #endif
  596.             }
  597.             regparse = next;
  598.             goto nest_check;
  599.         }
  600.         regsawbracket++;    /* remember we clobbered exp */
  601.         if (iter > 0) {
  602.             ch = *max;
  603.             sprintf(regparse,"%.*d", max-regparse, iter - 1);
  604.             *max = ch;
  605.             if (*max == ',' && max[1] != '}') {
  606.             if (atoi(max+1) <= 0)
  607.                 fatal("Can't do {n,m} with n > m");
  608.             ch = *next;
  609.             sprintf(max+1,"%.*d", next-(max+1), atoi(max+1) - 1);
  610.             *next = ch;
  611.             }
  612.             if (iter != 1 || *max == ',') {
  613.             regparse = origparse;    /* back up input pointer */
  614.             regnpar = orignpar;    /* don't make more parens */
  615.             }
  616.             else {
  617.             regparse = next;
  618.             goto nest_check;
  619.             }
  620.             *flagp = flags;
  621.             return ret;
  622.         }
  623.         if (*max == ',') {
  624.             max++;
  625.             iter = atoi(max);
  626.             if (max == next) {        /* any number more? */
  627.             regparse = next;
  628.             op = '*';        /* fake up one with a star */
  629.             }
  630.             else if (iter > 0) {
  631.             op = '?';        /* fake up optional atom */
  632.             ch = *next;
  633.             sprintf(max,"%.*d", next-max, iter - 1);
  634.             *next = ch;
  635.             if (iter == 1)
  636.                 regparse = next;
  637.             else {
  638.                 regparse = origparse - 1; /* offset ++ below */
  639.                 regnpar = orignpar;
  640.             }
  641.             }
  642.             else
  643.             fatal("Can't do {n,0}");
  644.         }
  645.         else
  646.             fatal("Can't do {0}");
  647.         }
  648.     }
  649.  
  650.     if (!ISMULT1(op)) {
  651.         *flagp = flags;
  652.         return(ret);
  653.     }
  654.  
  655.     if (!(flags&HASWIDTH) && op != '?')
  656.         FAIL("regexp *+ operand could be empty");
  657.     *flagp = (op != '+') ? (WORST|SPSTART) : (WORST|HASWIDTH);
  658.  
  659.     if (op == '*' && (flags&SIMPLE))
  660.         reginsert(STAR, ret);
  661.     else if (op == '*') {
  662.         /* Emit x* as (x&|), where & means "self". */
  663.         reginsert(BRANCH, ret);            /* Either x */
  664.         regoptail(ret, regnode(BACK));        /* and loop */
  665.         regoptail(ret, ret);            /* back */
  666.         regtail(ret, regnode(BRANCH));        /* or */
  667.         regtail(ret, regnode(NOTHING));        /* null. */
  668.     } else if (op == '+' && (flags&SIMPLE))
  669.         reginsert(PLUS, ret);
  670.     else if (op == '+') {
  671.         /* Emit x+ as x(&|), where & means "self". */
  672.         next = regnode(BRANCH);            /* Either */
  673.         regtail(ret, next);
  674.         regtail(regnode(BACK), ret);        /* loop back */
  675.         regtail(next, regnode(BRANCH));        /* or */
  676.         regtail(ret, regnode(NOTHING));        /* null. */
  677.     } else if (op == '?') {
  678.         /* Emit x? as (x|) */
  679.         reginsert(BRANCH, ret);            /* Either x */
  680.         regtail(ret, regnode(BRANCH));        /* or */
  681.         next = regnode(NOTHING);        /* null. */
  682.         regtail(ret, next);
  683.         regoptail(ret, next);
  684.     }
  685.       nest_check:
  686.     regparse++;
  687.     if (ISMULT2(regparse))
  688.         FAIL("nested *?+ in regexp");
  689.  
  690.     return(ret);
  691. }
  692.  
  693. /*
  694.  - regatom - the lowest level
  695.  *
  696.  * Optimization:  gobbles an entire sequence of ordinary characters so that
  697.  * it can turn them into a single node, which is smaller to store and
  698.  * faster to run.  Backslashed characters are exceptions, each becoming a
  699.  * separate node; the code is simpler that way and it's not worth fixing.
  700.  *
  701.  * [Yes, it is worth fixing, some scripts can run twice the speed.]
  702.  */
  703. static char *
  704. regatom(flagp)
  705. int *flagp;
  706. {
  707.     register char *ret;
  708.     int flags;
  709.  
  710.     *flagp = WORST;        /* Tentatively. */
  711.  
  712.     switch (*regparse++) {
  713.     case '^':
  714.         ret = regnode(BOL);
  715.         break;
  716.     case '$':
  717.         ret = regnode(EOL);
  718.         break;
  719.     case '.':
  720.         ret = regnode(ANY);
  721.         *flagp |= HASWIDTH|SIMPLE;
  722.         break;
  723.     case '[':
  724.         ret = regclass();
  725.         *flagp |= HASWIDTH|SIMPLE;
  726.         break;
  727.     case '(':
  728.         ret = reg(1, &flags);
  729.         if (ret == NULL)
  730.             return(NULL);
  731.         *flagp |= flags&(HASWIDTH|SPSTART);
  732.         break;
  733.     case '|':
  734.     case ')':
  735.         FAIL("internal urp in regexp");    /* Supposed to be caught earlier. */
  736.         break;
  737.     case '?':
  738.     case '+':
  739.     case '*':
  740.         FAIL("?+* follows nothing in regexp");
  741.         break;
  742.     case '\\':
  743.         switch (*regparse) {
  744.         case 'w':
  745.             ret = regnode(ALNUM);
  746.             *flagp |= HASWIDTH|SIMPLE;
  747.             regparse++;
  748.             break;
  749.         case 'W':
  750.             ret = regnode(NALNUM);
  751.             *flagp |= HASWIDTH|SIMPLE;
  752.             regparse++;
  753.             break;
  754.         case 'b':
  755.             ret = regnode(BOUND);
  756.             *flagp |= SIMPLE;
  757.             regparse++;
  758.             break;
  759.         case 'B':
  760.             ret = regnode(NBOUND);
  761.             *flagp |= SIMPLE;
  762.             regparse++;
  763.             break;
  764.         case 's':
  765.             ret = regnode(SPACE);
  766.             *flagp |= HASWIDTH|SIMPLE;
  767.             regparse++;
  768.             break;
  769.         case 'S':
  770.             ret = regnode(NSPACE);
  771.             *flagp |= HASWIDTH|SIMPLE;
  772.             regparse++;
  773.             break;
  774.         case 'd':
  775.             ret = regnode(DIGIT);
  776.             *flagp |= HASWIDTH|SIMPLE;
  777.             regparse++;
  778.             break;
  779.         case 'D':
  780.             ret = regnode(NDIGIT);
  781.             *flagp |= HASWIDTH|SIMPLE;
  782.             regparse++;
  783.             break;
  784.         case 'n':
  785.         case 'r':
  786.         case 't':
  787.         case 'f':
  788.         case 'e':
  789.         case 'a':
  790.         case 'x':
  791.         case 'c':
  792.         case '0':
  793.             goto defchar;
  794.         case '1': case '2': case '3': case '4':
  795.         case '5': case '6': case '7': case '8': case '9':
  796.             {
  797.                 int num = atoi(regparse);
  798.  
  799.                 if (num > 9 && num >= regnpar)
  800.                 goto defchar;
  801.                 else {
  802.                 regsawback = 1;
  803.                 ret = reganode(REF, num);
  804.                 while (isDIGIT(*regparse))
  805.                     regparse++;
  806.                 *flagp |= SIMPLE;
  807.                 }
  808.             }
  809.             break;
  810.         case '\0':
  811.             if (regparse >= regxend)
  812.                 FAIL("trailing \\ in regexp");
  813.             /* FALL THROUGH */
  814.         default:
  815.             goto defchar;
  816.         }
  817.         break;
  818.     default: {
  819.             register int len;
  820.             register char ender;
  821.             register char *p;
  822.             char *oldp;
  823.             int numlen;
  824.  
  825.             defchar:
  826.             ret = regnode(EXACTLY);
  827.             regc(0);        /* save spot for len */
  828.             for (len=0, p=regparse-1;
  829.               len < 127 && p < regxend;
  830.               len++)
  831.             {
  832.                 oldp = p;
  833.                 switch (*p) {
  834.                 case '^':
  835.                 case '$':
  836.                 case '.':
  837.                 case '[':
  838.                 case '(':
  839.                 case ')':
  840.                 case '|':
  841.                 goto loopdone;
  842.                 case '\\':
  843.                 switch (*++p) {
  844.                 case 'w':
  845.                 case 'W':
  846.                 case 'b':
  847.                 case 'B':
  848.                 case 's':
  849.                 case 'S':
  850.                 case 'd':
  851.                 case 'D':
  852.                     --p;
  853.                     goto loopdone;
  854.                 case 'n':
  855.                     ender = '\n';
  856.                     p++;
  857.                     break;
  858.                 case 'r':
  859.                     ender = '\r';
  860.                     p++;
  861.                     break;
  862.                 case 't':
  863.                     ender = '\t';
  864.                     p++;
  865.                     break;
  866.                 case 'f':
  867.                     ender = '\f';
  868.                     p++;
  869.                     break;
  870.                 case 'e':
  871.                     ender = '\033';
  872.                     p++;
  873.                     break;
  874.                 case 'a':
  875.                     ender = '\007';
  876.                     p++;
  877.                     break;
  878.                 case 'x':
  879.                     ender = scanhex(++p, 2, &numlen);
  880.                     p += numlen;
  881.                     break;
  882.                 case 'c':
  883.                     p++;
  884.                     ender = *p++;
  885.                     if (isLOWER(ender))
  886.                     ender = toupper(ender);
  887.                     ender ^= 64;
  888.                     break;
  889.                 case '0': case '1': case '2': case '3':case '4':
  890.                 case '5': case '6': case '7': case '8':case '9':
  891.                     if (*p == '0' ||
  892.                       (isDIGIT(p[1]) && atoi(p) >= regnpar) ) {
  893.                     ender = scanoct(p, 3, &numlen);
  894.                     p += numlen;
  895.                     }
  896.                     else {
  897.                     --p;
  898.                     goto loopdone;
  899.                     }
  900.                     break;
  901.                 case '\0':
  902.                     if (p >= regxend)
  903.                     FAIL("trailing \\ in regexp");
  904.                     /* FALL THROUGH */
  905.                 default:
  906.                     ender = *p++;
  907.                     break;
  908.                 }
  909.                 break;
  910.                 default:
  911.                 ender = *p++;
  912.                 break;
  913.                 }
  914.                 if (regfold && isUPPER(ender))
  915.                     ender = tolower(ender);
  916.                 if (ISMULT2(p)) { /* Back off on ?+*. */
  917.                 if (len)
  918.                     p = oldp;
  919.                 else {
  920.                     len++;
  921.                     regc(ender);
  922.                 }
  923.                 break;
  924.                 }
  925.                 regc(ender);
  926.             }
  927.             loopdone:
  928.             regparse = p;
  929.             if (len <= 0)
  930.                 FAIL("internal disaster in regexp");
  931.             *flagp |= HASWIDTH;
  932.             if (len == 1)
  933.                 *flagp |= SIMPLE;
  934.             if (regcode != ®dummy)
  935.                 *OPERAND(ret) = len;
  936.             regc('\0');
  937.         }
  938.         break;
  939.     }
  940.  
  941.     return(ret);
  942. }
  943.  
  944. static void
  945. regset(bits,def,c)
  946. char *bits;
  947. int def;
  948. register int c;
  949. {
  950.     if (regcode == ®dummy)
  951.         return;
  952.     c &= 255;
  953.     if (def)
  954.         bits[c >> 3] &= ~(1 << (c & 7));
  955.     else
  956.         bits[c >> 3] |=  (1 << (c & 7));
  957. }
  958.  
  959. static char *
  960. regclass()
  961. {
  962.     register char *bits;
  963.     register int class;
  964.     register int lastclass;
  965.     register int range = 0;
  966.     register char *ret;
  967.     register int def;
  968.     int numlen;
  969.  
  970.     ret = regnode(ANYOF);
  971.     if (*regparse == '^') {    /* Complement of range. */
  972.         regparse++;
  973.         def = 0;
  974.     } else {
  975.         def = 255;
  976.     }
  977.     bits = regcode;
  978.     for (class = 0; class < 32; class++)
  979.         regc(def);
  980.     if (*regparse == ']' || *regparse == '-')
  981.         goto skipcond;        /* allow 1st char to be ] or - */
  982.     while (regparse < regxend && *regparse != ']') {
  983.           skipcond:
  984.         class = UCHARAT(regparse++);
  985.         if (class == '\\') {
  986.             class = UCHARAT(regparse++);
  987.             switch (class) {
  988.             case 'w':
  989.                 for (class = 0; class < 256; class++)
  990.                     if (isALNUM(class))
  991.                     regset(bits,def,class);
  992.                 lastclass = 1234;
  993.                 continue;
  994.             case 'W':
  995.                 for (class = 0; class < 256; class++)
  996.                     if (!isALNUM(class))
  997.                     regset(bits,def,class);
  998.                 lastclass = 1234;
  999.                 continue;
  1000.             case 's':
  1001.                 for (class = 0; class < 256; class++)
  1002.                     if (isSPACE(class))
  1003.                     regset(bits,def,class);
  1004.                 lastclass = 1234;
  1005.                 continue;
  1006.             case 'S':
  1007.                 for (class = 0; class < 256; class++)
  1008.                     if (!isSPACE(class))
  1009.                     regset(bits,def,class);
  1010.                 lastclass = 1234;
  1011.                 continue;
  1012.             case 'd':
  1013.                 for (class = '0'; class <= '9'; class++)
  1014.                     regset(bits,def,class);
  1015.                 lastclass = 1234;
  1016.                 continue;
  1017.             case 'D':
  1018.                 for (class = 0; class < '0'; class++)
  1019.                     regset(bits,def,class);
  1020.                 for (class = '9' + 1; class < 256; class++)
  1021.                     regset(bits,def,class);
  1022.                 lastclass = 1234;
  1023.                 continue;
  1024.             case 'n':
  1025.                 class = '\n';
  1026.                 break;
  1027.             case 'r':
  1028.                 class = '\r';
  1029.                 break;
  1030.             case 't':
  1031.                 class = '\t';
  1032.                 break;
  1033.             case 'f':
  1034.                 class = '\f';
  1035.                 break;
  1036.             case 'b':
  1037.                 class = '\b';
  1038.                 break;
  1039.             case 'e':
  1040.                 class = '\033';
  1041.                 break;
  1042.             case 'a':
  1043.                 class = '\007';
  1044.                 break;
  1045.             case 'x':
  1046.                 class = scanhex(regparse, 2, &numlen);
  1047.                 regparse += numlen;
  1048.                 break;
  1049.             case 'c':
  1050.                 class = *regparse++;
  1051.                 if (isLOWER(class))
  1052.                     class = toupper(class);
  1053.                 class ^= 64;
  1054.                 break;
  1055.             case '0': case '1': case '2': case '3': case '4':
  1056.             case '5': case '6': case '7': case '8': case '9':
  1057.                 class = scanoct(--regparse, 3, &numlen);
  1058.                 regparse += numlen;
  1059.                 break;
  1060.             }
  1061.         }
  1062.         if (range) {
  1063.             if (lastclass > class)
  1064.                 FAIL("invalid [] range in regexp");
  1065.             range = 0;
  1066.         }
  1067.         else {
  1068.             lastclass = class;
  1069.             if (*regparse == '-' && regparse+1 < regxend &&
  1070.                 regparse[1] != ']') {
  1071.                 regparse++;
  1072.                 range = 1;
  1073.                 continue;    /* do it next time */
  1074.             }
  1075.         }
  1076.         for ( ; lastclass <= class; lastclass++) {
  1077.             regset(bits,def,lastclass);
  1078.             if (regfold && isUPPER(lastclass))
  1079.                 regset(bits,def,tolower(lastclass));
  1080.         }
  1081.         lastclass = class;
  1082.     }
  1083.     if (*regparse != ']')
  1084.         FAIL("unmatched [] in regexp");
  1085.     regparse++;
  1086.     return ret;
  1087. }
  1088.  
  1089. /*
  1090.  - regnode - emit a node
  1091.  */
  1092. static char *            /* Location. */
  1093. regnode(op)
  1094. char op;
  1095. {
  1096.     register char *ret;
  1097.     register char *ptr;
  1098.  
  1099.     ret = regcode;
  1100.     if (ret == ®dummy) {
  1101. #ifdef REGALIGN
  1102.         if (!(regsize & 1))
  1103.             regsize++;
  1104. #endif
  1105.         regsize += 3;
  1106.         return(ret);
  1107.     }
  1108.  
  1109. #ifdef REGALIGN
  1110. #ifndef lint
  1111.     if (!((long)ret & 1))
  1112.         *ret++ = 127;
  1113. #endif
  1114. #endif
  1115.     ptr = ret;
  1116.     *ptr++ = op;
  1117.     *ptr++ = '\0';        /* Null "next" pointer. */
  1118.     *ptr++ = '\0';
  1119.     regcode = ptr;
  1120.  
  1121.     return(ret);
  1122. }
  1123.  
  1124. /*
  1125.  - reganode - emit a node with an argument
  1126.  */
  1127. static char *            /* Location. */
  1128. reganode(op, arg)
  1129. char op;
  1130. unsigned short arg;
  1131. {
  1132.     register char *ret;
  1133.     register char *ptr;
  1134.  
  1135.     ret = regcode;
  1136.     if (ret == ®dummy) {
  1137. #ifdef REGALIGN
  1138.         if (!(regsize & 1))
  1139.             regsize++;
  1140. #endif
  1141.         regsize += 5;
  1142.         return(ret);
  1143.     }
  1144.  
  1145. #ifdef REGALIGN
  1146. #ifndef lint
  1147.     if (!((long)ret & 1))
  1148.         *ret++ = 127;
  1149. #endif
  1150. #endif
  1151.     ptr = ret;
  1152.     *ptr++ = op;
  1153.     *ptr++ = '\0';        /* Null "next" pointer. */
  1154.     *ptr++ = '\0';
  1155. #ifdef REGALIGN
  1156.     *(unsigned short *)(ret+3) = arg;
  1157. #else
  1158.     ret[3] = arg >> 8; ret[4] = arg & 0377;
  1159. #endif
  1160.     ptr += 2;
  1161.     regcode = ptr;
  1162.  
  1163.     return(ret);
  1164. }
  1165.  
  1166. /*
  1167.  - regc - emit (if appropriate) a byte of code
  1168.  */
  1169. static void
  1170. regc(b)
  1171. char b;
  1172. {
  1173.     if (regcode != ®dummy)
  1174.         *regcode++ = b;
  1175.     else
  1176.         regsize++;
  1177. }
  1178.  
  1179. /*
  1180.  - reginsert - insert an operator in front of already-emitted operand
  1181.  *
  1182.  * Means relocating the operand.
  1183.  */
  1184. static void
  1185. reginsert(op, opnd)
  1186. char op;
  1187. char *opnd;
  1188. {
  1189.     register char *src;
  1190.     register char *dst;
  1191.     register char *place;
  1192.     register offset = (op == CURLY ? 4 : 0);
  1193.  
  1194.     if (regcode == ®dummy) {
  1195. #ifdef REGALIGN
  1196.         regsize += 4 + offset;
  1197. #else
  1198.         regsize += 3 + offset;
  1199. #endif
  1200.         return;
  1201.     }
  1202.  
  1203.     src = regcode;
  1204. #ifdef REGALIGN
  1205.     regcode += 4 + offset;
  1206. #else
  1207.     regcode += 3 + offset;
  1208. #endif
  1209.     dst = regcode;
  1210.     while (src > opnd)
  1211.         *--dst = *--src;
  1212.  
  1213.     place = opnd;        /* Op node, where operand used to be. */
  1214.     *place++ = op;
  1215.     *place++ = '\0';
  1216.     *place++ = '\0';
  1217.     while (offset-- > 0)
  1218.         *place++ = '\0';
  1219. #ifdef REGALIGN
  1220.     *place++ = '\177';
  1221. #endif
  1222. }
  1223.  
  1224. /*
  1225.  - regtail - set the next-pointer at the end of a node chain
  1226.  */
  1227. static void
  1228. regtail(p, val)
  1229. char *p;
  1230. char *val;
  1231. {
  1232.     register char *scan;
  1233.     register char *temp;
  1234.     register int offset;
  1235.  
  1236.     if (p == ®dummy)
  1237.         return;
  1238.  
  1239.     /* Find last node. */
  1240.     scan = p;
  1241.     for (;;) {
  1242.         temp = regnext(scan);
  1243.         if (temp == NULL)
  1244.             break;
  1245.         scan = temp;
  1246.     }
  1247.  
  1248. #ifdef REGALIGN
  1249.     offset = val - scan;
  1250. #ifndef lint
  1251.     *(short*)(scan+1) = offset;
  1252. #else
  1253.     offset = offset;
  1254. #endif
  1255. #else
  1256.     if (OP(scan) == BACK)
  1257.         offset = scan - val;
  1258.     else
  1259.         offset = val - scan;
  1260.     *(scan+1) = (offset>>8)&0377;
  1261.     *(scan+2) = offset&0377;
  1262. #endif
  1263. }
  1264.  
  1265. /*
  1266.  - regoptail - regtail on operand of first argument; nop if operandless
  1267.  */
  1268. static void
  1269. regoptail(p, val)
  1270. char *p;
  1271. char *val;
  1272. {
  1273.     /* "Operandless" and "op != BRANCH" are synonymous in practice. */
  1274.     if (p == NULL || p == ®dummy || OP(p) != BRANCH)
  1275.         return;
  1276.     regtail(NEXTOPER(p), val);
  1277. }
  1278.  
  1279. /*
  1280.  - regcurly - a little FSA that accepts {\d+,?\d*}
  1281.  */
  1282. STATIC int
  1283. regcurly(s)
  1284. register char *s;
  1285. {
  1286.     if (*s++ != '{')
  1287.     return FALSE;
  1288.     if (!isDIGIT(*s))
  1289.     return FALSE;
  1290.     while (isDIGIT(*s))
  1291.     s++;
  1292.     if (*s == ',')
  1293.     s++;
  1294.     while (isDIGIT(*s))
  1295.     s++;
  1296.     if (*s != '}')
  1297.     return FALSE;
  1298.     return TRUE;
  1299. }
  1300.  
  1301. #ifdef DEBUGGING
  1302.  
  1303. /*
  1304.  - regdump - dump a regexp onto stderr in vaguely comprehensible form
  1305.  */
  1306. void
  1307. regdump(r)
  1308. regexp *r;
  1309. {
  1310.     register char *s;
  1311.     register char op = EXACTLY;    /* Arbitrary non-END op. */
  1312.     register char *next;
  1313.  
  1314.  
  1315.     s = r->program + 1;
  1316.     while (op != END) {    /* While that wasn't END last time... */
  1317. #ifdef REGALIGN
  1318.         if (!((long)s & 1))
  1319.             s++;
  1320. #endif
  1321.         op = OP(s);
  1322. #ifdef macintosh
  1323.         fprintf(perldbg,"%2d%s", s-r->program, regprop(s));    /* Where, what. */
  1324. #else
  1325.         fprintf(stderr,"%2d%s", s-r->program, regprop(s));    /* Where, what. */
  1326. #endif
  1327.         next = regnext(s);
  1328.         s += regarglen[op];
  1329. #ifdef macintosh
  1330.         if (next == NULL)        /* Next ptr. */
  1331.             fprintf(perldbg,"(0)");
  1332.         else 
  1333.             fprintf(perldbg,"(%d)", (s-r->program)+(next-s));
  1334. #else
  1335.         if (next == NULL)        /* Next ptr. */
  1336.             fprintf(stderr,"(0)");
  1337.         else 
  1338.             fprintf(stderr,"(%d)", (s-r->program)+(next-s));
  1339. #endif
  1340.         s += 3;
  1341.         if (op == ANYOF) {
  1342.             s += 32;
  1343.         }
  1344.         if (op == EXACTLY) {
  1345.             /* Literal string, where present. */
  1346.             s++;
  1347.             while (*s != '\0') {
  1348.                 (void)putchar(*s);
  1349.                 s++;
  1350.             }
  1351.             s++;
  1352.         }
  1353.         (void)putchar('\n');
  1354.     }
  1355.  
  1356. #ifdef macintosh
  1357.     /* Header fields of interest. */
  1358.     if (r->regstart)
  1359.         fprintf(perldbg,"start `%s' ", r->regstart->str_ptr);
  1360.     if (r->regstclass)
  1361.         fprintf(perldbg,"stclass `%s' ", regprop(r->regstclass));
  1362.     if (r->reganch & ROPT_ANCH)
  1363.         fprintf(perldbg,"anchored ");
  1364.     if (r->reganch & ROPT_SKIP)
  1365.         fprintf(perldbg,"plus ");
  1366.     if (r->reganch & ROPT_IMPLICIT)
  1367.         fprintf(perldbg,"implicit ");
  1368.     if (r->regmust != NULL)
  1369.         fprintf(perldbg,"must have \"%s\" back %d ", r->regmust->str_ptr,
  1370.           r->regback);
  1371.     fprintf(perldbg, "minlen %d ", r->minlen);
  1372.     fprintf(perldbg,"\n");
  1373. #else
  1374.     /* Header fields of interest. */
  1375.     if (r->regstart)
  1376.         fprintf(stderr,"start `%s' ", r->regstart->str_ptr);
  1377.     if (r->regstclass)
  1378.         fprintf(stderr,"stclass `%s' ", regprop(r->regstclass));
  1379.     if (r->reganch & ROPT_ANCH)
  1380.         fprintf(stderr,"anchored ");
  1381.     if (r->reganch & ROPT_SKIP)
  1382.         fprintf(stderr,"plus ");
  1383.     if (r->reganch & ROPT_IMPLICIT)
  1384.         fprintf(stderr,"implicit ");
  1385.     if (r->regmust != NULL)
  1386.         fprintf(stderr,"must have \"%s\" back %d ", r->regmust->str_ptr,
  1387.           r->regback);
  1388.     fprintf(stderr, "minlen %d ", r->minlen);
  1389.     fprintf(stderr,"\n");
  1390. #endif
  1391. }
  1392.  
  1393. /*
  1394.  - regprop - printable representation of opcode
  1395.  */
  1396. char *
  1397. regprop(op)
  1398. char *op;
  1399. {
  1400.     register char *p;
  1401.  
  1402.     (void) strcpy(buf, ":");
  1403.  
  1404.     switch (OP(op)) {
  1405.     case BOL:
  1406.         p = "BOL";
  1407.         break;
  1408.     case EOL:
  1409.         p = "EOL";
  1410.         break;
  1411.     case ANY:
  1412.         p = "ANY";
  1413.         break;
  1414.     case ANYOF:
  1415.         p = "ANYOF";
  1416.         break;
  1417.     case BRANCH:
  1418.         p = "BRANCH";
  1419.         break;
  1420.     case EXACTLY:
  1421.         p = "EXACTLY";
  1422.         break;
  1423.     case NOTHING:
  1424.         p = "NOTHING";
  1425.         break;
  1426.     case BACK:
  1427.         p = "BACK";
  1428.         break;
  1429.     case END:
  1430.         p = "END";
  1431.         break;
  1432.     case ALNUM:
  1433.         p = "ALNUM";
  1434.         break;
  1435.     case NALNUM:
  1436.         p = "NALNUM";
  1437.         break;
  1438.     case BOUND:
  1439.         p = "BOUND";
  1440.         break;
  1441.     case NBOUND:
  1442.         p = "NBOUND";
  1443.         break;
  1444.     case SPACE:
  1445.         p = "SPACE";
  1446.         break;
  1447.     case NSPACE:
  1448.         p = "NSPACE";
  1449.         break;
  1450.     case DIGIT:
  1451.         p = "DIGIT";
  1452.         break;
  1453.     case NDIGIT:
  1454.         p = "NDIGIT";
  1455.         break;
  1456.     case CURLY:
  1457.         (void)sprintf(buf+strlen(buf), "CURLY {%d,%d}",
  1458.             ARG1(op),ARG2(op));
  1459.         p = NULL;
  1460.         break;
  1461.     case REF:
  1462.         (void)sprintf(buf+strlen(buf), "REF%d", ARG1(op));
  1463.         p = NULL;
  1464.         break;
  1465.     case OPEN:
  1466.         (void)sprintf(buf+strlen(buf), "OPEN%d", ARG1(op));
  1467.         p = NULL;
  1468.         break;
  1469.     case CLOSE:
  1470.         (void)sprintf(buf+strlen(buf), "CLOSE%d", ARG1(op));
  1471.         p = NULL;
  1472.         break;
  1473.     case STAR:
  1474.         p = "STAR";
  1475.         break;
  1476.     case PLUS:
  1477.         p = "PLUS";
  1478.         break;
  1479.     default:
  1480.         FAIL("corrupted regexp opcode");
  1481.     }
  1482.     if (p != NULL)
  1483.         (void) strcat(buf, p);
  1484.     return(buf);
  1485. }
  1486. #endif /* DEBUGGING */
  1487.  
  1488. void
  1489. regfree(r)
  1490. struct regexp *r;
  1491. {
  1492.     if (r->precomp) {
  1493.         Safefree(r->precomp);
  1494.         r->precomp = Nullch;
  1495.     }
  1496.     if (r->subbase) {
  1497.         Safefree(r->subbase);
  1498.         r->subbase = Nullch;
  1499.     }
  1500.     if (r->regmust) {
  1501.         str_free(r->regmust);
  1502.         r->regmust = Nullstr;
  1503.     }
  1504.     if (r->regstart) {
  1505.         str_free(r->regstart);
  1506.         r->regstart = Nullstr;
  1507.     }
  1508.     Safefree(r->startp);
  1509.     Safefree(r->endp);
  1510.     Safefree(r);
  1511. }
  1512.